#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;

class Solution
{
private:
    vector<int> tmp;
    vector<vector<int>> ans;

public:
    vector<vector<int>> subsetsWithDup(vector<int> &nums)
    {
        sort(nums.begin(),nums.end());
        vector<bool> used(nums.size(), false);
        Helper(nums,0,used);
        return ans;
    }

    void Helper(const vector<int> &nums, int ix, vector<bool> &used)
    {
        ans.push_back(vector<int>(tmp));
        if (ix >= nums.size())
        {
            return;
        }

        for (int i = ix; i < nums.size(); i++)
        {
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])
            {
                continue;
            }
            tmp.push_back(nums[i]);
            used[i] = true;
            Helper(nums, i + 1, used);
            used[i] = false;
            tmp.pop_back();
        }
    }
};

// int main()
// {
//     Solution solu = Solution();
//     vector<int> input = {4,4,4, 1, 4};
//     solu.subsetsWithDup(input);
//     int i = 1;
//     return 0;
// }